package dp

func wordBreak(s string, wordDict []string) bool {
	wordMap := make(map[string]bool)
	for _, v := range wordDict {
		wordMap[v] = true
	}
	mem := make([]int, len(s))
	return dfs(s, 0, wordMap, mem)
}

func dfs(s string, start int, wordMap map[string]bool, mem []int) bool {
	if start == len(s) {
		return true
	}

	if mem[start] == 1 {
		return true
	}

	if mem[start] == -1 {
		return false
	}

	for i := start; i < len(s); i++ {
		left := s[start : i+1]
		if wordMap[left] && dfs(s, i+1, wordMap, mem) {
			mem[start] = 1
			return true
		}
	}
	mem[start] = -1
	return false
}

func wordBreakDp(s string, wordDict []string) bool {
	wordMap := make(map[string]bool)
	for _, v := range wordDict {
		wordMap[v] = true
	}

	n := len(s)

	dp := make([]bool, n+1)
	dp[0] = true

	// l代表的长度，即长度为l在dp表中的状态，index代表的是下标
	// 长度为l的字符串满足题目条件，则要同时满足两个条件，第一个是前缀子串s[0:index-1],由于dp表中下标都代表长度，因此子串s[0:index-1]
	// 对应到dp表中为dp[index],这里为什么子串不是[0:index]? 假设我们子串取[0:index],那么长度则为index + 1,dp表对应的
	// 下标也为index + 1,当第一次循环时，l=1,index=0,则dp[1] = dp[index +1] && check,即dp[1] = dp[1] && check，dp[1]的状态无法通过dp[1]获取，因此只能从
	// s[0:index-1] 开始截取子串
	for l := 1; l <= n; l++ {
		for index := 0; index < l; index++ {
			dp[l] = dp[index] && wordMap[s[index:l]]
			// 这里符合条件必须马上跳出，否则有可能此时值为true,在后续遍历中值为false，将true给更新掉
			if dp[l] {
				break
			}
		}
	}
	return dp[len(s)]

}
